class Solution:

    # 时间复杂度：O(nlogn)
    # 空间复杂度：O(1)
    def hIndex1(self, citations: List[int]) -> int:
        left, right = 0, len(citations)
        while left < right:
            mid = left + (right - left + 1) // 2

            cnt = 0
            for c in citations:
                if c >= mid:
                    cnt += 1

            if cnt >= mid:
                left = mid
            else:
                right = mid - 1

        return left

    def hIndex2(self, citations: List[int]) -> int:
        citations.sort()
        n = len(citations)
        # bug 修复，h 不能等于 0，否则数组越界异常
        for h in range(n, 0, -1):
            if citations[n - h] >= h:
                return h
        return 0

    def hIndex3(self, citations: List[int]) -> int:
        citations.sort()
        n = len(citations)
        left, right = 0, n
        while left < right:
            h = left + (right - left + 1) // 2
            if citations[n - h] >= h:
                left = h
            else:
                right = h - 1
        return left

    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        counter = [0] * (n + 1)
        for i in range(n):
            if citations[i] >= n:
                counter[n] += 1
            else:
                counter[citations[i]] += 1

        total = 0
        for h in range(n, -1, -1):
            total += counter[h]
            if total >= h:
                return h

        return 0